'''
冒泡排序 以及优化算法
2021-8-16 Nasa
'''

from test24random_list import sjlb

def sort_bubble(lb):
    # 右边界, 如果右边已经排序(不需要交换),下次交换到右边界就不再交换了
    b = len(lb) - 1
    for i in range(len(lb)):
        # 是否已经排好序了, 如果此次循环没有发生交换, 之后就不用再判断了, 直接退出循环
        k = True
        for j in range(b):
            if lb[j] > lb[j + 1]:
                lb[j], lb[j + 1] = lb[j + 1], lb[j]
                k = False
                b = j
                print(lb)
            s[0] += 1

        if k:
            print('break',lb)
            break
    return lb

if __name__ == '__main__':
    s = [0]
    l = [5, 9, 13, 1, 4, 20, 6, 6, 19, 27]
    l = sjlb(100,100)
    l=[71, 60, 92, 7, 69, 50, 42, 19, 56, 89, 16, 1, 53, 22, 79, 73, 6, 82, 62, 100, 41, 1, 31, 37, 24, 68, 99, 60, 22, 30, 69, 86, 73, 86, 14, 70, 42, 72, 46, 20, 80, 68, 38, 68, 51, 41, 39, 48, 4, 32, 47, 88, 86, 10, 15, 45, 34, 58, 11, 55, 14, 71, 100, 90, 91, 67, 57, 30, 91, 25, 95, 49, 85]

    # print(l)
    # print(len(sort_bubble(l)),s[0],s[0]/len(sort_bubble(l)))
    print(sort_bubble(l))